package jiaoheng.数据结构;

import lombok.Data;

public class s5二叉树 {
    // 如果是从root节点开始，从上到下，从左到右填充节点
    // 填充后的树，正好是一颗完全二叉树，或满二叉树，或者是个平衡树
    // 数字依次是 8 4 12 2 6 10 14 1 3 5 7 9 11 13 15

    // 应该有个插入逻辑,而不是一个Node一个Node地设置
    public static BinaryTree createATree(){
        BinaryTree binaryTree = new BinaryTree();
        int[] arr = {8,4,12,2,6,10,14,1,3,5,7,9,11,13,15};
        for(int i=0;i<arr.length;i++){
            binaryTree.addNode(binaryTree.getRoot(),new TreeNode(arr[i]));
        }
        return binaryTree;
    }

    public static BinaryTree handleCreateATree(){
        BinaryTree binaryTree = new BinaryTree();
        TreeNode rootTreeNode8 = new TreeNode(8);
        // 下面的顺序没必要，照着图画就对了
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode12 = new TreeNode(12);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode10 = new TreeNode(10);
        TreeNode treeNode14 = new TreeNode(14);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode9 = new TreeNode(9);
        TreeNode treeNode11 = new TreeNode(11);
        TreeNode treeNode13 = new TreeNode(13);
        TreeNode treeNode15 = new TreeNode(15);
        binaryTree.setRoot(rootTreeNode8);
        rootTreeNode8.setLeft(treeNode4);
        rootTreeNode8.setRight(treeNode12);
        treeNode4.setLeft(treeNode2);
        treeNode4.setRight(treeNode6);
        treeNode12.setLeft(treeNode10);
        treeNode12.setRight(treeNode14);
        treeNode2.setLeft(treeNode1);
        treeNode2.setRight(treeNode3);
        treeNode6.setLeft(treeNode5);
        treeNode6.setRight(treeNode7);
        treeNode10.setLeft(treeNode9);
        treeNode10.setRight(treeNode11);
        treeNode14.setLeft(treeNode13);
        treeNode14.setRight(treeNode15);
        return binaryTree;
    }



    public static void main(String[] args) {
        BinaryTree binaryTree = createATree();
        binaryTree.middleSort(binaryTree.getRoot());
    }

}

/**
 *
 * 二叉树
 * 非线性标结构
 * 既然二分查找法很快，很自然地就想到树形结构
 * 下面创造一个最简单的二叉树，按二叉搜索树规则插入数据，不要求平衡
 *
 */
@Data
class BinaryTree{
    private TreeNode root;

    public void addNode(TreeNode rootNode,TreeNode newNode){
        if(rootNode==null){
            this.setRoot(newNode);
            return;
        }
        if(newNode.getValue()<rootNode.getValue()){
            if(rootNode.getLeft()==null){
                rootNode.setLeft(newNode);
            }else{
                addNode(rootNode.getLeft(),newNode);
            }
        }else{
            if(rootNode.getRight()==null){
                rootNode.setRight(newNode);
            }else{
                addNode(rootNode.getRight(),newNode);
            }
        }
    }

    public void middleSort(TreeNode treeNode){
        if(treeNode.getLeft()!=null){
            middleSort(treeNode.getLeft());
        }
        System.out.println(treeNode.getValue()+" ");
        if(treeNode.getRight()!=null){
            middleSort(treeNode.getRight());
        }
    }


}

@Data
class TreeNode{
    private int value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(int value){
        this.value=value;
    }
}
